package Class031_位;

import java.util.HashSet;

public class BitManipulation {
    public static void main(String[] args) {
        test();

    }

    //将[l, r]范围的数全部与操作
    //因为0和任何数&都是0
    //实际上要看r最右边的1是否能留住
    //假设r是010010101011000
    //当l < r时，最右的1无法留住
    //然后把右边的1去除，继续看去除后的r是否还是 > l
    public static int and(int l, int r) {
        while (l < r) {
            r -= r & (-r);
        }
        return r;
    }

    //把一个数的二进制位逆序
    //eg: 10101101 => 10110101
    //10101010 => 01010101
    //
    public static int reverse(int num) {
        num = ((num & 0xaaaaaaaa) >>> 1) | ((num & 0x55555555) << 1);
        num = ((num & 0xcccccccc) >>> 2) | ((num & 0x33333333) << 2);
        num = ((num & 0xf0f0f0f0) >>> 4) | ((num & 0x0f0f0f0f) << 4);
        num = ((num & 0xff00ff00) >>> 8) | ((num & 0x00ff00ff) << 8);
//        num = ((num & 0xffff0000) >>> 16) | ((num & 0x0000ffff) << 16);
        num = (num >>> 16) | (num << 16);
        return num;
    }

    //位图
    //因一个整数有32位，可以利用其所有的位来表示某一个数是否存在
    //为什么用位图，因为省空间。1比32
    //但是，必须是连续的区间，比如[0,100]
    //那么，需要100个位来表示。
    //需要多少整数?
    //若一共有0~31个，那么只需要1个整数即可。也就是n个整数，需要n / 32然后向上取整
    //(n + 32 - 1) / 32 个
    //位图需要 add(把num加入位图), remove(移除位图), reverse(如果位图没有num, 就加入，反之删除), contains
    public static class BitMap {
        public int[] bitmap;
        private int zeroes;
        private int ones;
        private boolean reverse;

        //n就是要表示的整数的上限
        public BitMap(int n) {
            bitmap = new int[(n + 31) / 32];
        }

        public void add(int num) {
            int pos = num / 32;
            if(!inRange(pos)) {
                System.out.println("超出范围");
                return;
            }
            if(contains(num)) {
//                System.out.println("请勿重复添加");
                return;
            }
            bitmap[pos] |= 1 << (num % 32);
        }

        public void remove(int num) {
            int pos = num / 32;
            if(!inRange(pos)) {
                System.out.println("超出范围");
                return;
            }
            if(!contains(num)) {
                return;
            }
            bitmap[pos] &= ~(1 << (num % 32));
        }

        public void reverse(int num) {
            if(contains(num)) remove(num);
            else add(num);
        }

        public void flip() {

        }

        public boolean all() {
            return false;
        }

        public boolean one() {
            return false;
        }

        public int count() {
            return -1;
        }

        public String toString() {
            return "";
        }

        public boolean contains(int num) {
            int pos = num / 32;
            return inRange(pos) && ((bitmap[pos] >>> (num % 32)) & 1) != 0;
        }

        private boolean inRange(int pos) {
            return pos < bitmap.length;
        }
    }

    public static void test() {
        int max = 10000;
        int time = 100000;
        int err = 0;
        boolean correct = true;
        HashSet<Integer> set = new HashSet<>();
        BitMap bitMap = new BitMap(max);
        for(int i = 0; i < time; i++) {
            double prob = Math.random();
            int num = (int)(Math.random() * (max + 1));
            if(prob < 0.333) {
                //add
                set.add(num);
                bitMap.add(num);
            }else if(prob < 0.666) {
                //remove
                set.remove(num);
                bitMap.remove(num);
            }else {
                bitMap.reverse(num);
                if(set.contains(num)) set.remove(num);
                else set.add(num);
            }
        }
        for(int num = 0; num <= max; num++) {
            boolean setContains = set.contains(num);
            boolean mapContains = bitMap.contains(num);
            if(setContains != mapContains) {
                correct = false;
                err++;
                System.out.println("出现不同:");
                System.out.println("num " + num + "是否在set中:" + setContains);
                System.out.println("num " + num + "是否在map中:" + mapContains);
            }
        }
        if(correct) {
            System.out.println("All clear.");
        }else {
            System.out.println("Result:" + (time - err) + "/" + time);
            System.out.println("Accuracy:" + (time - err) * 1.0 / time);
        }

    }
}
